# -*- coding:utf-8
"""
作者: Jia
日期: 2022年04月17日
描述: https://leetcode-cn.com/problems/coin-change/
"""
from typing import List


class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        arr = [float('inf')] * (amount + 1)
        arr[0] = 0
        for i, num in enumerate(arr):
            for coin in coins:
                if i + coin < len(arr):
                    arr[i + coin] = min(arr[i + coin], arr[i] + 1)
        return arr[amount] if arr[amount] != float('inf') else -1


s = Solution()
s.coinChange([186, 419, 83, 408], 6249)
